package algorithms.a04heap;

import algorithms.utis.SortTestHelper;
import org.apache.commons.lang3.RandomUtils;

/**
 * 最小堆
 *
 * @author 王昊然
 * @create 2018-03-06 9:57
 **/
public class MinHeap<Item extends Comparable> {
    private int capacity;//容量，具体的数值是不包括首位的
    private int count = 0;//首位是不放到count统计中的
    private Item[] items;

    public MinHeap(int capacity) {
        this.capacity = capacity;//首位置空出
        items = (Item[]) new Comparable[capacity + 1];
    }

    public MinHeap(Item[] coms) {
        this.capacity = coms.length;
        items = (Item[]) new Comparable[this.capacity + 1];

        for (int i = 0; i < coms.length; i++) {
            items[i + 1] = coms[i];
        }

        this.count = coms.length;

        //从最后一个有子节点的节点开始，向上遍历shiftDown
        for (int i = count/2; i > 0; i--) {
            shiftDown(i);
        }




    }

    public void insert(Item e) {
        assert (count < capacity);

        count++;
        items[count] = e;

        this.shiftUp(count);
    }

    public Item extractMin() {

        assert (count > 0);

        Item min = items[1];
        items[1] = items[count];
        count--;
        this.shiftDown(1);
        return min;

    }


    /**
     * 上移
     *
     * @param i 下标
     * @date: 2018/3/6 10:24
     * @author: 王昊然
     */
    private void shiftUp(int i) {

        Item now = items[i];

        while (i > 1) {
            int parent = i / 2;
            if (items[parent].compareTo(now) > 0) {
                items[i] = items[parent];
                i = parent;
            } else {
                break;
            }
        }

        items[i] = now;
    }

    /**
     * 下移
     *
     * @param i
     * @date: 2018/3/6 11:26
     * @author: 王昊然
     */
    private void shiftDown(int i) {

        Item e = items[i];

        while (2 * i <= count) {//有子节点，才循环

            //默认左叶子节点最小
            int base = 2 * i;
            Item minChild = items[base];

            //判断左右叶子节点谁最小
            int right = 2 * i + 1;
            if (right <= count && items[right].compareTo(minChild) < 0) {
                minChild = items[right];
                base = right;
            }

            //e与最小叶子比较
            if (minChild.compareTo(e) < 0) {
                items[i] = minChild;
                i = base;
            } else {
                break;
            }
        }

        items[i] = e;
    }

    public boolean isEmpty() {
        return count == 0;
    }
    public int size() {
        return count;
    }
    public Item[] getData() {
        return items;
    }

    public static void main(String[] args) {
        MinHeap<Integer> heap = new MinHeap<>(10);
        testInsert(heap);
        testExtractMin(heap);
    }

    private static void testInsert(MinHeap heap) {

        int count = heap.getData().length - 1;
        while (count > 0) {
            heap.insert(RandomUtils.nextInt(1, 100));
            count--;
        }
        System.out.println(SortTestHelper.printArray(heap.getData()));
    }

    private static void testExtractMin(MinHeap heap) {

        while (!heap.isEmpty()) {
            System.out.println(heap.extractMin());
        }

    }
}
